0576. 出界的路径数【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 动态规划

1. 📝 题目描述

• leetcode

给你一个大小为 m x n 的网格和一个球。球的起始坐标为 [startRow, startColumn]。你可以将球移到在四个方向上相邻的单元格内（可以穿过网格边界到达网格之外）。你 最多 可以移动 maxMove 次球。

给你五个整数 m、n、maxMove、startRow 以及 startColumn，找出并返回可以将球移出边界的路径数量。因为答案可能非常大，返回对 10^9 + 7 取余 后的结果。

---

示例 1：

输入：m = 2, n = 2, maxMove = 2, startRow = 0, startColumn = 0
输出：6

示例 2：

输入：m = 1, n = 3, maxMove = 3, startRow = 0, startColumn = 1
输出：12

---

提示：

• 1 <= m, n <= 50
• 0 <= maxMove <= 50
• 0 <= startRow < m
• 0 <= startColumn < n

2. 🎯 s.1 - 动态规划

c

int findPaths(int m, int n, int maxMove, int startRow, int startColumn) {
    long long MOD = 1000000007;
    long long dp[50][50], ndp[50][50];
    memset(dp, 0, sizeof(dp));
    dp[startRow][startColumn] = 1;
    long long res = 0;
    int dirs[4][2] = {{1,0},{-1,0},{0,1},{0,-1}};
    for (int k = 0; k < maxMove; k++) {
        memset(ndp, 0, sizeof(ndp));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] == 0) continue;
                for (int d = 0; d < 4; d++) {
                    int ni = i + dirs[d][0], nj = j + dirs[d][1];
                    if (ni < 0 || ni >= m || nj < 0 || nj >= n) {
                        res = (res + dp[i][j]) % MOD;
                    } else {
                        ndp[ni][nj] = (ndp[ni][nj] + dp[i][j]) % MOD;
                    }
                }
            }
        }
        memcpy(dp, ndp, sizeof(dp));
    }
    return (int)res;
}

js

/**
 * @param {number} m
 * @param {number} n
 * @param {number} maxMove
 * @param {number} startRow
 * @param {number} startColumn
 * @return {number}
 */
var findPaths = function (m, n, maxMove, startRow, startColumn) {
  const MOD = 1e9 + 7
  let dp = Array.from({ length: m }, () => new Array(n).fill(0))
  dp[startRow][startColumn] = 1
  let res = 0
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ]
  for (let k = 0; k < maxMove; k++) {
    const ndp = Array.from({ length: m }, () => new Array(n).fill(0))
    for (let i = 0; i < m; i++) {
      for (let j = 0; j < n; j++) {
        if (dp[i][j] === 0) continue
        for (const [di, dj] of dirs) {
          const ni = i + di,
            nj = j + dj
          if (ni < 0 || ni >= m || nj < 0 || nj >= n) {
            res = (res + dp[i][j]) % MOD
          } else {
            ndp[ni][nj] = (ndp[ni][nj] + dp[i][j]) % MOD
          }
        }
      }
    }
    dp = ndp
  }
  return res
}

py

class Solution:
    def findPaths(self, m: int, n: int, maxMove: int, startRow: int, startColumn: int) -> int:
        MOD = 10**9 + 7
        dp = [[0] * n for _ in range(m)]
        dp[startRow][startColumn] = 1
        res = 0
        for _ in range(maxMove):
            ndp = [[0] * n for _ in range(m)]
            for i in range(m):
                for j in range(n):
                    if dp[i][j] == 0:
                        continue
                    for di, dj in ((1,0),(-1,0),(0,1),(0,-1)):
                        ni, nj = i + di, j + dj
                        if ni < 0 or ni >= m or nj < 0 or nj >= n:
                            res = (res + dp[i][j]) % MOD
                        else:
                            ndp[ni][nj] = (ndp[ni][nj] + dp[i][j]) % MOD
            dp = ndp
        return res

• 时间复杂度：$O(maxMove\times m\times n)$
• 空间复杂度：$O(m\times n)$

算法思路：

• dp[i][j] 表示当前步数下走到位置 (i,j) 的路径数
• 每一步向四个方向扩展，走出边界则累加到结果，否则转移到新位置